Database systems store, retrieve, and process information. One type of database system is a relational database. In a relational database, the relationship of data are usually maintained in a table having rows and columns. The rows organize instances of related data, and the columns group data having common characteristics or attributes.
The operation of locating data in a database system is called a query. Typically, queries are expressed in a query language, e.g., structured query language (SQL). In a query, the expressions which determine the search criteria are called predicates. Predicates can be phrased in terms of a range of values, for example, greater than (>), less than or equal (≦), equal (=), between, and the like. Predicates can further include mathematical relationships. Predicates can also be related by logical operators, for example, AND (Λ), OR (V), NOT (−), and the like.
Processing queries is typically a time consuming task since a database system can include a large amount of data, and a given query may need to retrieve data from different portions of a database system. Conventional database systems, therefore, typically include a query optimizer that transforms a given query into an equivalent optimized query which may be processed more efficiently than the given query. In addition, to more efficiently handle large amounts of data, tables and indexes within a database system can be partitioned.
With respect to indexes (e.g., partitioned indexes and non-partitioned indexes),                conventional database systems, however, generally impose restrictions on the nature of        predicates that can be utilized by a query optimizer on an index. That is, conventional        query optimizers typically use only matching predicates. A matching predicate is either        an inequality on the first column of a multi-column index, or a matching predicate could        involve equalities on the first few columns of a multicolumn index followed by an inequality with no gaps. So, for example, if an index has four columns c1, c2, c3 c4, then        c1=5 and c2=10 and c3>=15 is a matching predicate. On the other hand c1 =5 and        c2=10 and c4>=15 is not a matching predicate since there is a gap between c2 and c4. In this case we can use c1=5 and c2=10 as a matching predicate. However, on many occasions predicates other than matching predicates—e.g., screening predicates or stage 1 predicates—could potentially be used for partition pruning.        
Accordingly, what is needed is a query optimizer that can provide greater partition pruning ability than conventional query optimizers, including utilizing predicates on columns other than a leading column, e.g., screening predicates or stage 1 predicates, to determine partitions that need to be scanned, and hence partitions that can be pruned, to satisfy a query. The present invention addresses such a need.